package dynamicprogramming;

import org.junit.Test;

/**
 * @author DuJiabao
 * @create 2021-01-01 16:16
 */
public class DynamicProgrammingMethod3 extends Example2 {

    @Override
    public void f(int[] items, int[] value, int n, int w) {
        int[][] state = new int[n][w + 1];
        // 保险起见，全都先变成-1
        for (int i = 0; i < n; i++) {
            for (int i1 = 0; i1 < w; i1++) {
                state[i][i1] = -1;
            }
        }
        //第一个物品
        state[0][0] = 0; //不放
        state[0][items[0]] = value[0]; //放

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < w + 1; j++) {
                if (state[i - 1][j] >= 0) {
                    state[i][j] = state[i - 1][j]; // 不放！
                }
            }
            // 放
            for (int j = 0; j <= w - items[i]; j++) {
                state[i][j + items[i]] = Math.max(state[i][j + items[i]], value[i] + state[i - 1][j]); // 如果比原来的大，就放。
            }
        }
        // 找出最大的
        for (int i = 0; i < w + 1; i++) {
            maxV = Math.max(state[n - 1][i], maxV);
        }
    }

    @Test
    public void test() {
        f(items, value, n, w);
        System.out.println(maxV);
    }

}
